package com.vincent.algorithms.sort;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 希尔排序 1959年Shell发明；第一个突破O(n^2)的排序算法；是简单插入排序的改进版；
 * 它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序,是一种插入排序。它是直接插入排序算法的一种威力加强版
 *
 * 算法描述：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
 *把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
 *随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序
 *
 * 希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差
 * 几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法.
 *
 * 希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量(即 代码实现中的n/2 )时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(n^1.5)，
 * 希尔排序时间复杂度的下界是n*log2n
 * 平均时间复杂度 O(Nlog2 N) 第一个图片O(n^2)的排序算法  据说一般 O(n^1.5)
 * 最好情况下时间复杂度 O(Nlog2 N)
 * 空间复杂度 O(1)
 * 稳定性 稳定
 *
 *
 * 最原始的那种增量，即从length逐步减半，其实这还不算最快的希尔，有几个增量在实践中表现更出色，具体可以看weiss的数据结构书，
 * 同时里面有希尔排序复杂度的证明，但是涉及组合数学和数论，希尔排序是实现简单但是分析极其困难的一个算法的例子至于楼主问为啥希尔能突破O(N^2)的界，
 * 可以用逆序数来理解，假设我们要从小到大排序，一个数组中取两个元素如果前面比后面大，则为一个逆序，容易看出排序的本质就是消除逆序数，
 * 可以证明对于随机数组，逆序数是O(N^2)的，而如果采用“交换相邻元素”的办法来消除逆序，每次正好只消除一个，因此必须执行O(N^2)的交换次数，
 * 这就是为啥冒泡、插入等算法只能到平方级别的原因，反过来，基于交换元素的排序要想突破这个下界，必须执行一些比较，
 * 交换相隔比较远的元素，使得一次交换能消除一个以上的逆序，希尔、快排、堆排等等算法都是交换比较远的元素，只不过规则各不同罢了
 * Created by yangwenchang on 2017/8/23.
 */
public class ShellSort implements Sort{

    /**
     * 这是严格按照希尔排序定义 的写法  需要4层循环嵌套 代码略显繁琐
     *
     * 可改进点：各分组排序  由顺序进行 改为 交叉进行  可减少一层循环
     *
     * @param array
     * @param c
     * @param <T>
     */
    @Override
    public <T> void sort(T[] array, Comparator<? super T> c) {
        int swapCount = 0;
        int compareCount = 0;

        for (int gap = array.length/2;gap>0;gap = gap/2){
//            以gap为间隔 分为array.length/gap 组
            for(int index=0;index<array.length/gap;index++) {
//            对每组采用直接插入排序方法
                for (int i = 1; i < array.length / gap; i++) {

//                    注意这个地方可能的 gap*index+j<array.length 防止数组越界
                    for (int j = i; j > 0 && gap*index+j<array.length ; j--) {
                        compareCount++;
                        if (c.compare(array[gap*index+j-1],array[gap*index+j])>0){
                            swapCount++;
                            Sort.swap(array,gap*index+j-1,gap*index+j);
                        }

                    }

                }
            }
        }

        System.out.println("总计交换次数:" + swapCount);
        System.out.println("总计比对次数:" + compareCount);

    }


    /**
     *
     * 按照各分组交叉进行比较
     * 0...gap-1 的数据都是各分组的第一个  gap gap+1..是各分组的第二个数据
     *
     * @param array
     * @param c
     * @param <T>
     */
    public <T> void sort2(T[] array, Comparator<? super T> c){

        int swapCount = 0;
        int compareCount = 0;

        for (int gap = array.length/2;gap>0;gap = gap/2){

            for (int i=gap;i<array.length;i++){

                for (int j=i-gap;j>=0;j-=gap){
//                    统计比较次数需要  不然可以放到 (j>=0 && c.compare(array[j],array[j+gap])>0)
//                    这个还可以减少比较次数
                    compareCount++;
                    if (c.compare(array[j],array[j+gap])>0){
                        swapCount++;
                        Sort.swap(array,j,j+gap);
                    }
                }

            }

        }

        System.out.println("总计交换次数:" + swapCount);
        System.out.println("总计比对次数:" + compareCount);


    }

    public static void main(String[] args) {

        Integer[] arr = {9,4,1,6,8,5};
        System.out.println(Arrays.asList(arr));
        new ShellSort().sort2(arr,(x,y)->x-y);
        System.out.println(Arrays.asList(arr));

    }
}
